package thired.class11_digui;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Class05_RobotWalk {
    public static int ways1(int N, int start, int aim, int K){
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start, K, aim, N);
    }

    public static int process1(int cur, int rest, int aim, int N) {
        if(rest == 0){
            return cur == aim ? 1 : 0;
        }
        // (cur, rest)
        if (cur == 1) { // 1 -> 2
            return process1(2, rest - 1, aim, N);
        }
        // (cur, rest)
        if (cur == N) { // N-1 <- N
            return process1(N - 1, rest - 1, aim, N);
        }
        return process1(cur - 1,rest - 1,aim,N) + process1(cur + 1,rest - 1,aim ,N);
    }

    public static int ways2(int N, int start, int aim, int K){
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] map = new int[N + 1][K + 1];
        for (int[] ints : map) {
            Arrays.fill(ints,-1);
        }
        return process2(start, K, aim, N,map);
    }

    public static int process2(int cur, int rest, int aim, int N,int[][] map) {
        if(map[cur][rest] != -1){
            return map[cur][rest];
        }
        if(rest == 0){
            map[cur][rest] = cur == aim ? 1 : 0;
            return cur == aim ? 1 : 0;
        }
        int ans = 0;
        // (cur, rest)
        if (cur == 1) { // 1 -> 2
            ans =  process2(2, rest - 1, aim, N,map);
        }else
        // (cur, rest)
        if (cur == N) { // N-1 <- N
            ans =  process2(N - 1, rest - 1, aim, N,map);
        }else {
            ans = process2(cur - 1,rest - 1,aim,N,map) + process2(cur + 1,rest - 1,aim ,N,map);
        }
        map[cur][rest] = ans;
        return ans;
    }

    public static int ways3(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1;
        //lie
        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];
                    //hang
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        // dp就是缓存表
        // dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
        // dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
        // N+1 * K+1
        return dp[start][K];
    }


    public static void main(String[] args) {
        System.out.println(ways1(5, 2, 4, 6));
        System.out.println(ways2(5, 2, 4, 6));
        System.out.println(ways3(5, 2, 4, 6));
    }
}
